//============================================================================
// Name        : lab6_1_2.cpp
// Author      : Binda
// Version     :
// Copyright   : Copyright © 2010- 2011 LAN. All Rights Reserved
// Description :布线问题
//============================================================================

#include <iostream>
#include<stdio.h>
using namespace std;
#define N 8
typedef struct {
	int row;
	int col;
} Position;
typedef struct {
	//struct Position;
	int row[10000];
	int col[10000];
	int end;
	int begin;
} Queue;
int grid[100][100];
Position start, finish;
int PathLen = 0;
Position * path;
int n, m, a, b, x;
void printGrid()
{
	 for(int i=0;i<N+2;i++){
				  for(int j=0;j<N+2;j++)
				  {
				     printf(" %.2d",grid[i][j]);
				  }
				  cout<<endl;
		}
}
bool FindPath(Position start, Position finish) {//计算从起点位置start到目标位置finish的最短布线路径，找到最短布线路//径则返回true，否则返回false
	if ((start.row == finish.row) && (start.col == finish.col)) {
		PathLen = 0;
		return true;
	} //start=finish
	//设置方格阵列“围墙”
	int i;
	for (i = 0; i <= m + 1; i++)
		grid[0][i] = grid[n + 1][i] = 1; //顶部和底部
	for (i = 0; i <= n + 1; i++)
		grid[i][0] = grid[i][m + 1] = 1; //左翼和右翼
	int j;
	//初始化相对位移
	Position offset[4];
	offset[0].row = 0;
	offset[0].col = 1;//右
	offset[1].row = 1;
	offset[1].col = 0;//下
	offset[2].row = 0;
	offset[2].col = -1;//左
	offset[3].row = -1;
	offset[3].col = 0;//上
	int NumOfNbrs = 4;//相邻方格数
	Position here, nbr;
	here.row = start.row;
	here.col = start.col;
	grid[start.row][start.col] = 2;
	//标记可达方格位置
	//LinkedQueue<Position> Q;
	Queue Q;
	Q.end = 0;
	Q.begin = 0;
	do {//标记相邻可达方格
		for (i = 0; i < NumOfNbrs; i++) {
			nbr.row = here.row + offset[i].row;
			nbr.col = here.col + offset[i].col;
			if (grid[nbr.row][nbr.col] == 0) {
				//该方格未被标记
				grid[nbr.row][nbr.col] = grid[here.row][here.col] + 1;//统计步数
				if ((nbr.row == finish.row) && (nbr.col == finish.col))
					break; //完成布线
				//Q.Add(nbr);
				Q.col[Q.end] = nbr.col;
				Q.row[Q.end] = nbr.row;
				Q.end++;
			}
		}
		//是否到达目标位置finish？
		if ((nbr.row == finish.row) && (nbr.col == finish.col)){
			//return true;
			break;//完成布线
		}
		//活结点队列是否非空？
		if (Q.begin == Q.end)
			return false;//无解
		else {
			here.row = Q.row[Q.begin];
			here.col = Q.col[Q.begin];
			Q.begin++;//取下一个扩展结点
		}
	} while (true);
	//构造最短布线路径
	PathLen = grid[finish.row][finish.col] - 2;
	path = new Position[PathLen];
	//从目标位置finish开始向起始位置回溯
	here = finish;
	for (j = PathLen - 1; j >= 0; j--) {
		path[j] = here;
		//找前驱位置
		for (i = 0; i < NumOfNbrs; i++) {
			nbr.row = here.row + offset[i].row;
			nbr.col = here.col + offset[i].col;
			if (grid[nbr.row][nbr.col] == j + 2)
				break;
		}
		here = nbr;//向前移动
	}
	return true;
}
int main() {
	int j;
	printf("输入电路板区域n*m和封锁的格数x:\n");
	//  cin>>n>>m>>x;
	n = 8;
	m = 8;
	// x=16;
	//printf("输入封锁的坐标:\n");
	for (a = 0; a < n + 2; a++)
		for (b = 0; b < m + 2; b++)
			grid[a][b] = 0;

	/* for( x = x ; x >= 1 ; x -- )
	 {
	 cin >> a >> b ;
	 grid[a][b]= 1;
	 }*/
	//设置障碍
	for (int i = 1; i <= 5; i++)
		for (int j = 4; j <= 5; j++)
			grid[i][j] = 1;

	for (int i = 6; i <= 8; i++)
		for (int j = 7; j <= 8; j++)
			grid[i][j] = 1;
     printGrid();
	//printf("输入起始位置和结束位置:\n");
	//cin>>start.row>>start.col>>finish.row>>finish.col;
	start.row = 3;
	start.col = 2;
	finish.row =5;
	finish.col = 6;
	if (FindPath(start, finish)) {
		printf("输出路径长度及途中坐标:");
		cout << PathLen << endl;
		cout << start.row << " " << start.col << endl;
		for (j = 0; j < PathLen; j++)
			cout << path[j].row << " " << path[j].col << endl;
	} else
	cout << "No Solution!" << endl;
	printGrid();
	delete[] path;
	return 0;
}
